package history.hot100.difficult;

// 76. 最小覆盖子串:https://leetcode-cn.com/problems/minimum-window-substring/
public class LeetCode_76 {
    public static void main(String[] args) {
        int []test = new int[100];
        System.out.println();
    }
    public String minWindow(String s, String t) {
        int []map = new int [128];
        for (char ch: t.toCharArray())
            map[ch]++;
        int count = t.length();
        int left = 0;
        int right = 0;
        int windowLength = Integer.MAX_VALUE;
        int strStart = 0;
        while (right < s.length()) {
            if (map[s.charAt(right++)]-- > 0)
                count--;
            while (count == 0) {
                if (right-left < windowLength) {
                    windowLength = right - left;
                    strStart = left;
                }
                if (map[s.charAt(left++)]++ == 0)
                    count++;
            }
        }
        if (windowLength != Integer.MAX_VALUE)
            return s.substring(strStart, strStart + windowLength);
        return "";
    }
}
